package 动态规划;

import java.util.Set;

public class p牛客CC12拆分词句 {
    public boolean wordBreak(String s, Set<String> dict) {
        int len=s.length();

        boolean[] canBroken=new boolean[len+1];//比字符串大 1 ，是因为人为要定义第一个状态
        canBroken[0]=true;//经过分析，只有第一个元素值为true，才不会影响后面的判断

        for (int i = 1; i <len; i++) {
            for (int j = 0; j <i; j++) {
                //根据状态转移方程，决定当前canBroken[i]的值
                if (canBroken[j] && dict.contains(s.substring(j,i))) {
                    //如果canBroken[j]为真，并且s的[j,i)子串存在于dict中，就将canBroken[i]=true,并结束内层循环
                    canBroken[i]=true;
                    break;
                }

            }
        }

        return canBroken[len];//canBroken[len]判断了字符串中的每个子串的结果，所以能代表最终的结果，boolean默认值为false
    }
}
